package 分类.回溯;

import java.util.LinkedList;
import java.util.List;

public class 组和总和 {
    static List<List<Integer>> res=new LinkedList<>();
    static LinkedList<Integer> track = new LinkedList<>();
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {


        back(target,0,candidates,0);
        return res;
    }

    static void back(int target,int sum,int[] nums,int start){
        if(sum==target){
            res.add(new LinkedList<>(track));
            return;
        }
        if(sum>target){
            return;
        }
        for (int i=start;i<nums.length;i++){
            track.add(nums[i]);
            sum+=nums[i];
            //不限制相同组成数字的数量
            back(target,sum,nums,i);
            //限制相同组成数字的数量
            back(target,sum,nums,i+1);
            sum-=nums[i];
            track.removeLast();
        }
    }



    public static void main(String[] args) {
        int[] nums={2,3,6,7};
        List<List<Integer>> res=combinationSum(nums,7);
        for (List<Integer> re : res) {
            for (Integer integer : re) {

                System.out.print(integer);

            }
            System.out.println();
        }
    }
}
